class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2)
            return 0;
        vector<bool> visit(n, false);

        int cnt = n / 2;
        for (int i = 3; i * i < n; i += 2)
        {
            if (!visit[i])
            {
                for (int j = i * i; j < n; j += 2 * i)
                {
                    if (!visit[j]) {
                        visit[j] = true;
                        cnt--;
                    }
                }
            }
        }

        return cnt;
    }
};